package Demo15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 串联所有单词的子串
 * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
 * 思想和 Demo14 是一样的
 * 把字符串当成是字符串看待,然后使用双指针+ 哈希表来实现 维护一个count来代表当前有效的字符串数组
 */

class Solution {
    public List<Integer> findSubstring(String ss, String[] words) {
        // 返回值
        List<Integer> ret = new ArrayList<>();
        // 存储 words 的表
        HashMap<String,Integer> hash2 = new HashMap();
        // 将 words 存储到 hash 表当中
        for(String str:words) {
            hash2.put(str,hash2.getOrDefault(str,0)+1);
        }
        int m = words.length,len = words[0].length();
        for(int i = 0;i < len;i++) {
            HashMap<String,Integer> hash1 = new HashMap<>();
            for(int left = i,right = i,count = 0;right + len <= ss.length();right += len) {
                // 1. 进窗口,维护count
                String in = ss.substring(right,right + len);
                hash1.put(in,hash1.getOrDefault(in,0)+1);
                if(hash1.get(in) <= hash2.getOrDefault(in,0))count++;

                // 2. 判断
                if(right - left + 1 > len * m) {
                    // 3. 出窗口,维护count
                    String out = ss.substring(left,left+len);
                    if(hash1.get(out) <= hash2.getOrDefault(out,0)) count--;
                    hash1.put(out,hash1.get(out) - 1);
                    if(hash1.get(out) == 0) hash1.remove(out);
                    left += len;
                }

                // 4.跟新返回值
                if(count == m) ret.add(left);
            }
        }
        return ret;
    }

    public List<Integer> findSubstring2(String ss, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();// 记录words 的元素的 长度, 这个字符串数组的元素的长度是一个的
        HashMap<String,Integer> hash2 = new HashMap<>();// 这个是用来记录words 字符串数组元素的
        // 遍历 words 将 words 的元素存储到 hash2 当中
        for(int i = 0; i < words.length;i++) {
            hash2.put(words[i],hash2.getOrDefault(words[i],0) + 1);
        }
        char[] s = ss.toCharArray(); // 将字符串 ss 转换成字符数组
        int m = words.length; // 字符串数组 words 的长度
        // 这里开遍历了
        for(int i = 0; i < len ;i++) {// 这个是代表滑动窗口要遍历的次数
            HashMap<String,Integer> hash1 = new HashMap<>();// 这个是用来统计 s 字符串的
            for(int left = i,right = i,count = 0;right <= s.length - len;right += len) {
                String in = String.valueOf(Arrays.copyOfRange(s,right,right + len));
                hash1.put(in,hash1.getOrDefault(in,0) + 1); // 入窗口
                if(hash2.get(in) != null) if(hash1.get(in) <= hash2.get(in)) count++; // 统计有效的字符串的数量

                if((right - left)/ len + 1 > m) { // 判断 滑动窗口的长度 是否比 words 的长度 长了

                    String out = String.valueOf(Arrays.copyOfRange(s,left,left + len));// 记录出窗口的字符串
                    if(hash2.get(out) != null)if(hash1.get(out) <= hash2.get(out)) count--; // 出窗口的是有效字符串, 需要xount--
                    hash1.put(out,hash1.get(out) - 1); // 出窗口
                    if(hash1.get(out) == 0) hash1.remove(out);
                    left += len;
                }
                if(count == m) list.add(left);
            }
        }
        return list;
    }


}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> list = solution.findSubstring("barfoothefoobarman",new String[] {"foo","bar"});
        System.out.println(list);
    }
}